package DataStructure.graph;

import DataStructure.linear.Queue;

import DataStructure.priority.MinPriorityQueue;
import DataStructure.uf.UF_Tree_Weighted;

public class KruskalMST {
    //保存最小生成树的所有边
    private Queue<Edge> mst;

    //索引代表顶点，使用uf.connect(v,w)可以判断v和w是否在同一树中，使用uf.union(v,w)可以把两棵树合并
    private UF_Tree_Weighted uf;
    //存储图中所有的边，使用最小优先队列，对边按照权重进行排序
    private MinPriorityQueue<Edge> pq;

    //根据一副加权无向图，创建最小生成树计算对象
    public KruskalMST(EdgeWeightedGraph G){
        //初始化mst
        this.mst=new Queue<Edge>();
        this.uf=new UF_Tree_Weighted(G.V());
        this.pq=new MinPriorityQueue<Edge>(G.E()+1);

        //把图中所有的边存储到pq中
        for (Edge e : G.edges()) {
            pq.insert(e);
        }

        //遍历pq队列，拿到最小权重的边进行处理
        while (!pq.isEmpty() && mst.size()<G.V()-1){
            //找到权重最小的边
            Edge e = pq.delMin();
            //找到边的两个顶点
            int v = e.either();
            int w = e.other(v);
            //判断两个顶点是否已经在同一颗树中，如果已经在同一颗树中则不做处理，如果不在则合并成一颗树
            if(uf.connected(v,w)){
                continue;
            }
            uf.union(v,w);
            //让边e进入到mst队列中
            mst.enqueue(e);
        }
    }

    //获取最小生成树中所有的边
    public Queue<Edge> edges(){
        return mst;
    }
}
